퀵정렬 {quick sort}

https://choiwheatley.notion.site/quick-sort-8720f36d603840f1b37fa73465c76eb0

20230518 estsoft - python - tree -- LIS -- selection sort -- insertion sort -- merge sort -- quick sort

TL;DR

Pseudo Code

유튜브 영상에서 보던 방식과는 조금 달라서 헤맸다. 실제 코드를 보면 two pointer개념을 사용하기는 하지만 pivot을 기점으로 물리적으로 분리된 공간에 실제로 데이터를 swap하는 것이 보였으나, 여기 방식에 따르면 일단 한쪽 끝 (아래 코드는 end)으로 피벗을 배치시킨 뒤에 pivot보다 작은 원소의 개수를 카운트 하고 incremental 하게 위치를 잡는 것을 볼 수 있다.

맨 마지막 줄이 중요한데, 피벗의 위치는 아직 끝이므로 본래 있어야 할 자리로 옮기는 것을 알 수 있다.

#include <random>
#include <utility>
static std::mt19937 engine{std::random_device{}()};
static std::uniform_int_distribution<unsigned int> generator{};

template <typename Iter, class Less>
Iter partition(Iter begin, Iter end, Less const &less) {
  auto pivot = begin + generator(engine) % (end - begin);
  std::swap(*pivot, *(end - 1));
  pivot = end - 1; // ==IMPORTANT== pivot is currently end of the sequence
  size_t count = 0; // pivot보다 작은 원소의 개수를 카운트
  for (auto cur = begin; cur != pivot; ++cur) {
    if (less(*cur, *pivot)) {
      // move element to left
	  // begin ~ begin + count => *pivot 보다 작은 원소들
	  // begin+count ~ cur => *pivot 보다 크거나 같은 원소들
      std::swap(*cur, *(begin + count));
      count += 1;
    }
  }
  // move pivot to right place
  std::swap(*pivot, *(begin + count));
  return begin + count;
}
template <typename Iter, class Less>
void sort(Iter begin, Iter end, Less const &less) {
  if (end - begin <= 1) {
    return;
  }
  auto mid = partition(begin, end, less);
  sort(begin, mid, less);
  sort(mid + 1, end, less);
}

pseudocode (python)

from typing import MutableSequence, Callable
from random import randint

def partition(ls: MutableSequence, lo: int, hi: int, less: Callable[[int, int], bool]):
    pivot_idx = randint(lo, hi - 1)
    # move pivot last of the element
    ls[pivot_idx], ls[hi - 1] = ls[hi - 1], ls[pivot_idx]
    pivot_idx = hi - 1

    count = 0  # count will be the separating point between less(x, pivot) and other
    for i in range(lo, pivot_idx):
        # iterate EXCEPT pivot
        if less(ls[i], ls[pivot_idx]):
            ls[i], ls[lo + count] = ls[lo + count], ls[i]
            count += 1
    # move pivot to the right place
    ls[pivot_idx], ls[lo + count] = ls[lo + count], ls[pivot_idx]
    return lo + count


def qsort(ls: MutableSequence, lo: int, hi: int, less: Callable[[int, int], bool]):
    """
    - lo: starting index (inclusive)
    - hi: end index (exclusive)
    - less: function that can customize ordering
    """
    if hi - lo <= 1:
        return
    pivot = partition(ls, lo, hi, less)
    qsort(ls, lo, pivot, less)
    qsort(ls, pivot + 1, hi, less)  # pivot은 넣으면 무한재귀

관련문제